package leetcode.code438;

import java.util.ArrayList;
import java.util.List;

public class Solution1 extends Solution438 {

	@Override
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> result = new ArrayList<>();
		if (p.length() > s.length()) {
			return result;
		}
		int[] dic = new int[26];
		for (int i = 0; i < p.length(); i++) {
			dic[p.charAt(i) - 'a'] += 1;
		}
		int ft = 0;// fast
		int sw = 0;// slow
		int lenp = p.length();// 找到答案的结束标识
		int count = 0;// ft-sw定长，count是在这个之间有效数量
		while (ft < lenp) {
			dic[s.charAt(ft) - 'a'] -= 1;
			if (dic[s.charAt(ft) - 'a'] >= 0) {
				count++;
			}
			ft++;
		}
		if (count == lenp) {
			result.add(sw);
		}
		while (ft < s.length()) {
			// cbaebabacd
			// 0123456789
			dic[s.charAt(sw) - 'a'] += 1;
			if (dic[s.charAt(sw) - 'a'] > 0) {
				count--;
			}
			dic[s.charAt(ft) - 'a'] -= 1;
			if (dic[s.charAt(ft) - 'a'] >= 0) {
				count++;
			}
			sw++;
			ft++;
			if (count == lenp) {
				result.add(sw);
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

//
//		System.out.println((int) 'a' - 'a');
//		System.out.println((int) 'z' - 'a');
//		System.out.println('z' - 'a');
	}

}
